class Solution {
public:

    int waysToStep(int n)
    {
        const int MOD = 1e9 + 7;
        if (n == 1)return 1;
        if (n == 2)return 2;
        if (n == 3)return 4;
        int a, b, c, d;
        a = 1, b = 2, c = 4;
        n -= 3;
        while (n--)
        {
            d = ((a + b) % MOD + c) % MOD;
            a = b, b = c, c = d;
        }
        return d;

    }
};